Not all pathfinding problems are the same. We need to split them into two categories based on the graph's properties.

Note: This slide lists Dijkstra and Topological Sort side-by-side only to contrast their purposes. Dijkstra (and BFS) are algorithms for finding shortest paths when edge weights or uniform distances matter. DFS and Topological Sort are algorithms for extracting structural information (an ordering) from a graph. They are not the same kind of tool — although on a DAG a topological order can be used to compute shortest paths in a single pass.

  • Problem 1: The "Weighted" Problem (e.g., GPS). Find the path with minimum total weight in a general graph (cycles allowed).
  • Use Dijkstra's Algorithm (for non-negative weights) — it directly solves shortest-paths by iterative relaxation, and works on graphs with cycles.
  • Problem 2: The "Structural" Problem (e.g., Task Dependencies). Find a linear ordering of nodes that respects dependency edges (an ordering, not a distance).
  • Topological Sort applies only to Directed Acyclic Graphs (DAGs); it reveals structure (an order), not distances.
  • Important note: on a DAG a topological order can be used to compute shortest paths in O(|V|+|E|) by relaxing edges once in topo order — so topo sort can be part of a shortest-path method, but its role is structural.
Practical tip: Shortest paths on a DAG (use topo order)
1# Given DAG G=(V,E) and source s, compute shortest paths in O(|V|+|E|)
2order = topological_sort(G)   # structural step
3for v in V: dist[v] = +infty
4dist[s] = 0
5for u in order:                        # relax each outgoing edge once
6    for (u,v,w) in outgoing_edges(u):
7        if dist[v] > dist[u] + w: dist[v] = dist[u] + w
8# result: dist[] are shortest distances from s in the DAG